package demo1;

import java.util.*;

public class Solution {

    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] count = new int[12];
        for(String s : words){
            count[f(s)]++;
        }
        for(int i = 9; i >= 1; i--){
            count[i] += count[i + 1];
        }
        int[] ans = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            String s = queries[i];
            ans[i] = count[f(s) + 1];
        }
        return ans;
    }
    public int f(String s){
        int cnt = 0;
        char x = 'z';
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c < x){
                x = c;
                cnt = 1;
            }else if(c == x){
                cnt++;
            }
        }
        return cnt;
    }


    public int[] numSmallerByFrequency2(String[] queries, String[] words) {
        int[] nums = new int[words.length];
        for(int i = 0; i < words.length; i++){
            nums[i] = f(words[i]);
        }
        Arrays.sort(nums);

        int[] ans = new int[queries.length];
        for(int i = 0; i < queries.length; i++){
            String s = queries[i];
            int l = 0, r = words.length;
            while(l < r){
                int mid = l + (r - l) / 2;
                if(nums[mid] <= f(s)){
                    l = mid + 1;
                }else{
                    r = mid;
                }
            }
            ans[i] = words.length - l;
        }
        return ans;
    }
    public int f2(String s){
        int[] cnt = new int[26];
        for(int i = 0; i < s.length(); i++){
            cnt[s.charAt(i) - 'a']++;
        }
        for(int x : cnt){
            if(x > 0) { return x;}
        }
        return 0;
    }

    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        for(int i = 1; i < nums.length; i++){
            nums[i] += nums[i - 1];
        }
        for(int i = 0; i < queries.length; i++){
            queries[i] = upperBound(nums, queries[i]);
        }
        return queries;
    }
    public int upperBound(int[] nums, int x){
        int left = -1, right = nums.length;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > x){
                right = mid;
            }else{
                left = mid;
            }
        }
        return right;
    }


    public static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);

        int ret = 0;
        for(int x : arr1){
            int low = x - d;
            int high = x + d;
            if(!binaryBound(arr2, low, high)){
                ret++;
            }
        }
        return ret;
    }

    public static boolean binaryBound(int[] nums, int low, int high){
        int l = 0, r = nums.length;
        while(l < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] >= low && nums[mid] <= high){
                return true;
            }else if(nums[mid] < high){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return false;
    }

    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int r = lowerBound(nums, i, upper - nums[i] + 1);
            int l = lowerBound(nums, i, lower - nums[i]);
            ans += r - l;
        }
        return ans;
    }
    public int lowerBound(int[] nums, int r, int x){
        int l = -1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(nums[mid] >= x){
                r = mid;
            }else{
                l = mid;
            }
        }
        return r;
    }

    public long countFairPairs2(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        long ans = 0;
        int l = nums.length, r = nums.length;
        for(int j = 0; j < nums.length; j++){
            while(r > 0 && nums[r - 1] > upper - nums[j]){
                r--;
            }
            while(l > 0 && nums[l - 1] >= lower - nums[j]){
                l--;
            }
            ans += Math.min(r, j) - Math.min(l, j);
        }
        return ans;
    }

    public long countFairPairs3(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        return count(nums, upper) - count(nums, lower - 1);
    }
    public long count(int[] nums, int x){
        long ans = 0;
        int j = nums.length - 1;
        for(int i = 0; i < nums.length; i++){
            while(j > i && nums[j] > x - nums[i]){
                j--;
            }
            if(j == i){
                break;
            }
            ans += j - i;
        }
        return ans;
    }

    public static void main(String[] args) {

        int[] n1 = new int[]{1,4,2,3};
        int[] n2 = new int[]{-4,-3,6,10,20,30};
        System.out.println(findTheDistanceValue(n1, n2,3));
    }
}
